import copy
class Solution(object):
    def rotateGrid(self, grid, k):
        m = len(grid)
        n = len(grid[0])
        new_grid = copy.deepcopy(grid)
        for t in range(min(m, n) // 2):
            d = []
            for i in range(t, m - 1 - t):
                d.append([i, t])
            for j in range(t, n - 1 - t):
                d.append([m - 1 - t, j])
            for i in range(m - 1 - t, t, -1):
                d.append([i, n - 1 - t])
            for j in range(n - 1 - t, t, -1):
                d.append([t, j])
            q = len(d)
            for index, item in enumerate(d):
                new_index = (index + k) % q
                new_item = d[new_index]
                new_grid[new_item[0]][new_item[1]] = grid[item[0]][item[1]]
        return new_grid
